package array;

/**
 * 给你一个整数数组 nums。在一次操作中，你可以选择一个子数组，并将其替换为一个等于该子数组 最大值 的单个元素。
 * 返回经过零次或多次操作后，数组仍为 非递减 的情况下，数组 可能的最大长度。
 * 子数组 是数组中一个连续、非空 的元素序列。
 * <p>
 * 示例 1：
 * 输入： nums = [4,2,5,3,5]
 * 输出： 3
 * 解释：
 * 实现最大长度的一种方法是：
 * 将子数组 nums[1..2] = [2, 5] 替换为 5 → [4, 5, 3, 5]。
 * 将子数组 nums[2..3] = [3, 5] 替换为 5 → [4, 5, 5]。
 * 最终数组 [4, 5, 5] 是非递减的，长度为 3。
 * <p>
 * 示例 2：
 * 输入： nums = [1,2,3]
 * 输出： 3
 * 解释：
 * 无需任何操作，因为数组 [1,2,3] 已经是非递减的。
 *
 * @author Jisheng Huang
 * @version 20250420
 */
public class MakeArrNonDecreasing_100554_2 {
    /**
     * Compare the current with the first number. If current number if less than the first, increment removes.
     * Then take the difference between the array length and removes
     *
     * @param nums the given array
     * @return the minimum number of remove to make the array non-decreasing
     */
    public static int maximumPossibleSize(int[] nums) {
        int removes = 0;
        int len = nums.length;
        int prev = nums[0];

        for (int i = 1; i < len; ++i) {
            prev = Math.max(prev, nums[i]);

            if (nums[i] < prev) {
                ++removes;
            }
        }

        return len - removes;
    }

    public static void main(String[] args) {
        int[] nums = {4, 2, 5, 3, 5};
        System.out.println(maximumPossibleSize(nums));

        nums = new int[]{1, 2, 3};
        System.out.println(maximumPossibleSize(nums));
    }
}
